网络流总结&做题记录

网络流 24 题

1.二分图

二分图对偶定理：

二分图最大权匹配 $=$ 二分图最小点权覆盖 $=$ $|∑w|$ $-$ 二分图最大点权独立集

1.最小点权覆盖

若一个点集 $P \subseteq V$ , 使得： $\forall(u,v) \in E$ , $(u \in P) \lor (v \in P)$ ，那么 $P$ 便是原图的一个点覆盖。

对于所有满足条件的 $P$ , $\sum_{u \in P} w_u$ 的最小值即为最小点权覆盖。

• 将二分图的两部分分别与源点/汇点连容量为点权的边

• 二分图内部的边容量设为 $+\infty$

最后图的最小割即为原二分图的最小点权覆盖。

考虑这样做的正确性：

二分图的点覆盖中每条边都至少被一个点覆盖，所以没有源点到汇点的路径，是新图的割。

新图的割的边集只可能包含源点与汇点为顶点的边（内部的边容量为 $+\infty$），那么割掉一条边对应选出这个点。

2.最大点权独立集

若一个点集 $P \subseteq V$ , 使得： $\forall(u,v) \in E$ , $(u \notin P) \lor (v \notin P)$ ， 那么 $P$ 便是原图的一个点独立集。

对于所有满足条件的 $P$ , $\sum_{u \in P} w_u$ 的最大值即为最大点权独立集。

由对偶定理和 1. 易得解法，不再赘述。

2.集合划分问题

类型一

将元素划分为两个集合 $A,B$ , 满足 $A \cup B = U$ 且 $A \cap B = \varnothing$。

划分的代价为：

$\sum_{i \in A}a_i+\sum_{i \in B}b_i$

同时给定一些关系，若元素 $u,v$ 不在同一集合则会有 $w_i$ 的代价。

求划分的最小代价。

• 将一个元素拆成两个点，分别表示选入 $A/B$ 集合。再从源点/汇点向两部分的点连容量为 $b_i/a_i$ 的边（注意容量是反的）。

• 元素之间的代价可视为 $(A_u,B_v)/(A_v,B_u)$ 之间连容量为 $w_i$ 的边。

• 在 $(A_u,B_u)$ 之间连容量为 $+\infty$ 的边。

图的最小割即为最小代价。

正确性？

因为 $(A_u,B_u)$ 之间的边容量为 $+\infty$ ， 不可能是原图的边割集。

所以 $A_u,B_u$ 之中一定有一点与源汇的边被割去，若 $(S,A_u)$ 被割则表示选入 $B$ 集合，反之若 $(B_u,T)$ 被割则选入 $A$ 集合。这也解释了建图时容量是相反的。

$(A_u,B_v),(A_v,B_u)$ 被割则表示接受 $w_i$ 的代价。显然 $(A_u,B_v),(A_v,B_u)$
$2$ 条边最多会被割 $1$ 条。

可以看出，图的割便是一个选择方案，选择方案也对应一个割。求出最小割即可。

$\text{eg.}$ P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

类型二

$\text{eg.}$ 2020.12.28 题目

3.方格问题

• 格子之间有要求

格点之间的要求视作边，若是二分图则是最大点权独立集。

$\text{eg.}$ P2774 方格取数问题 $~~~$ P3355 骑士共存问题

• 每行、每列、每个格子有要求

对于每行、每列分别建一个点

行与列之间的边对应格子限制，源点与行的边 / 汇点与列的边 对应 行 / 列 的限制。

值得注意的是，这个图也是一个二分图。

$\text{eg.}$ P4311 士兵占领 $~~~$ P4194 矩阵

4.最大权闭合子图

对于原图 $G=(V,E)$ 的一个子图 $G'=(V',E'=\{(u,v)| (u,v) \in E \land u \in V' \land v \in V'\})$，

若： $\forall u \in V', (u,v) \in E$ ，有 $v \in V'$，那么 $G'$ 为原图的闭合子图。

对于所有满足条件的 $G'$ ， $\sum_{u \in V'} w_u$ 的最大值即为原图的最大权闭合子图。

• 对于原图中点权为正的点 $u$，连接 $(s,u)$ , 容量为 $w_i$
  。

• 对于原图中点权为负的点 $v$，连接 $(v,t)$ ，容量为 $-w_i$。

• 对于原图中的边，连接 $(u,v)$ , 容量为 $+\infty$。

答案即为所有正权点的权值之和减去新图的最小割。

咕咕咕...

5.最大密度子图

对于原图 $G=(V,E)$ 的一个子图 $G'=(V',E'=\{(u,v)| (u,v) \in E \land u \in V' \land v \in V'\})$，

该子图的密度为： $D'=\frac{|E'|}{|V'|}$。

对于所有子图 $G'$ ，密度最大的子图即为原图的最大密度子图。

6.平面图最小割

总结在这篇文章里的。

2020.12.18 拆点、最大流

P3153 [CQOI2009]跳舞

二分答案 + 拆点 + 最大流

P3163 [CQOI2014]危桥

最大流

2020.12.19 最大流/最小割

*SP839 Optimal Marks

按位考虑 + 最小割

2020.12.21 上下界网络流

P4311 士兵占领

P4843 清理雪道

UVA1440 Inspection

2020.12.22 上下界网络流

P4194 矩阵

2020.12.23 拆点、最大流

UVA12125 March of the Penguins

拆点

*SP4063 Sell Pigs

最大流建模

2020.12.24 最大流/最小割

*P1344 [USACO4.4]Pollutant Control

特殊处理：

在最小割最小的前提下，让割的边最少。

对每一条 $(u,v,c)$ 的边变为 $(u,v,c \times base+1)$ 。$(base > m)$

最后 $\text{Maxflow} /base$ 为最小割， $\text{Maxflow}\%base$ 为最少边。

*P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

最小割建模

2020.12.25 最大流/最小割

UVA1660 Cable TV Network & SP300 Cable TV Network

最小割建模

*P4662 [BalticOI 2008]黑手党

最小割建模

P3191 [HNOI2007]紧急疏散

最大流建模

P2402 奶牛隐藏

最大流建模

2020.12.26 最大权闭合子图

CF1082G Petya and Graph

P4174 [NOI2006]最大获利

P3410 拍照

*P4177 [CEOI2008]order

注意经典模型的转换。

Solution

P3749 [六省联考2017]寿司餐厅

*CF103E Buying Sets

特殊条件的运用。

P5295 [北京省选集训2019]图的难题

结论题 + 退流

退流似乎用处不大，毕竟建图的时间肯定小于网络流的时间。

*2020.12.28 集合划分问题

P1361 小M的作物

P1935 [国家集训队]圈地计划

P4313 文理分科 & P1646 [国家集训队]happiness

P4210 土地划分

2020.12.28 最小割

P2598 [ZJOI2009]狼和羊的故事

最小割建模

P6094 [JSOI2015]圈地

上一题的加强版

2020.12.29 最小割

*P3227 [HNOI2013]切糕

最小割建模

P3973 [TJOI2015]线性代数

最小割建模

P5934 [清华集训2012]最小生成树

最小割建模

P1791 [国家集训队]人员雇佣

2020.12.30 二分图

*P5771 [JSOI2016]反质数序列

最大权独立集

P2172 [国家集训队]部落战争

最小路径覆盖

P4589 [TJOI2018]智力竞赛

最小路径覆盖

SP741 STEAD - Steady Cow Assignment

二分图匹配

UVA1194 Machine Schedule

最小点权覆盖

2020.12.30

P6062 [USACO05JAN]Muddy Fields G

CF1404E Bricks

P4055 [JSOI2009]游戏

P2825 [HEOI2016/TJOI2016]游戏

todo list

最大闭合子图，最大密度子图，集合划分类型二总结

P2805 [NOI2009]植物大战僵尸

UVA1389 Hard Life